import netscape.security.UserTarget;

import java.util.PriorityQueue;
import java.util.Random;

class Solution1 {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0; i<k; i++) {
            queue.add(nums[i]);
        }
        for(int i = k; i<nums.length; i++) {
            if(nums[i] > queue.peek()) {
                queue.poll();
                queue.add(nums[i]);
            }
        }
        return queue.peek();
    }
}
// 7
//1 2 7 3 4 3 8 9 6
class Solution2 {
    public void swap(int[] nums,int a,int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
    public int qsort(int[] nums,int begin,int end, int k) {
        Random random = new Random();
        int key = nums[random.nextInt(end-begin+1)+begin];
        int left = begin-1, right = end+1, i = begin;
        while(i<right) {
            if(nums[i] > key) {
                swap(nums,--right,i);
            }else if(nums[i] < key) {
                swap(nums,++left,i++);
            }else {
                i++;
            }
        }
        //分类讨论
        //[1,left] [left+1,right-1] [right,r]
        //    a            b            c
        int b = right - left - 1, c = end - right + 1;
        if(c>=k) return qsort(nums,right,end,k);
        else if(b+c>=k) return key;
        else return qsort(nums,begin,left,k-b-c);
    }
    public int findKthLargest(int[] nums, int k) {
        int key = qsort(nums,0,nums.length-1,k);
        return key;
    }
}
class Solution {
    public void swap(int[] nums,int a,int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
    public void qsort(int[] nums,int begin,int end,int k) {
        Random random = new Random();
        int key = nums[random.nextInt(end-begin+1)+begin];
        int left = begin-1,right = end+1, i = begin;
        while(i<right) {
            if(nums[i] < key) {
                swap(nums,++left,i++);
            } else if(nums[i] > key) {
                swap(nums,--right,i);
            }else {
                i++;
            }
        }

        //分类讨论
        //[1,left] [left+1,right-1] [right,r]
        //    a            b            c
        int  a = left-begin+1, b = right - left - 1, c = end - right + 1;
        if(a+b>=k) {
            return;
        }else if(a>k) {
            qsort(nums,begin,left,k);
        }else {
            qsort(nums,right,end,k-a-b);
        }
    }
    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock,0, stock.length-1,cnt);
        int[] ret = new int[cnt];
        for(int i = 0; i<cnt; i++) {
            ret[i] = stock[i];
        }
        return ret;
    }
}
// 1 2 3 4 5
public class Test {

}
